﻿// Copyright (c) 2023 刻BITTER
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.


#pragma once

#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <initializer_list>

namespace data_basic {

    namespace _hide {
        template <bool fit_in_8, bool fit_in_16, bool fit_in_32>
        struct _enough_index_type {
        };


        template <>
        struct _enough_index_type<true, true, true> {
            using type = uint8_t;
        };


        template <>
        struct _enough_index_type<false, true, true> {
            using type = uint16_t;
        };


        template <>
        struct _enough_index_type<false, false, true> {
            using type = uint32_t;
        };


        template <>
        struct _enough_index_type<false, false, false> {
            using type = uint64_t;
        };
    }  // namespace _hide


    /**
     * @breif 根据所需的bit flag 数量，选择最小能容纳的整数类型
     *
     * 若所需数量为8，则可用uint8_t，若数量为10，则可用uint16_t，依此类推。
     *
     */
    template <size_t Count>
    struct enough_bit_flag_type {
        using type = typename _hide::_enough_index_type<Count <= 8, Count <= 16, Count <= 32>::type;
    };

    template <size_t Count>
    using enough_bit_flag_type_t = typename enough_bit_flag_type<Count>::type;


    /**
     * @breif 根据所需索引的元素数量，选择最小能容纳的整数类型
     *
     * 若列表最多元素数量为100，则可用uint8_t 索引其中每个元素；若元素数量为1000，则需要用uint16_t。
     *
     */
    template <size_t Count>
    struct enough_index_type {
        using type = typename _hide::_enough_index_type<Count <= UINT8_MAX, Count <= UINT16_MAX, Count <= UINT64_MAX>::type;
    };

    template <size_t Count>
    using enough_index_type_t = typename enough_index_type<Count>::type;

    /**
     * @brief 单向链表节点
     *
     * 注意，next 指针必须放在第一个成员位置。
     *
     * @tparam NodeDataType
     */
    template <typename NodeDataType>
    struct LinkNode {
        LinkNode *next;
        NodeDataType data;
    };


    template <typename T>
    void swap(LinkNode<T> &lhs, LinkNode<T> &rhs) {
        // 链表节点的交换应该只交换内部值，不改变节点在表中的位置，也就是不交换next 指针
        // 因为存在指向这个节点的上一个节点。
        // 比如，若有四个节点 <1> <2> <3> <4>， 若只交换<2> <3> 节点中的next 指针，由于节点<1> 没变，结构就变成：
        // <1> <2> <4>
        // <2> 本来指向<3> ，交换后改为指向<4>，节点<3> 自己指向自己，没有其他节点持有指向<3> 指针，于是<3> 就从链表中消失了。
        swap(lhs.data, rhs.data);
    }


    // 可以把另一个结构体嵌入LinkNode 中，将其扩展成双向节点, 这样做的目的是复用LinkNode 的基础设施
    // template <typename NodeDataType>
    // struct _NestedBackwardNode {
    //     LinkNode<_NestedBackwardNode<NodeDataType>> *prev;
    //     NodeDataType data;
    // };


    // template <typename T>
    // void swap(LinkNode<_NestedBackwardNode<T>> &lhs, LinkNode<_NestedBackwardNode<T>> &rhs) {
    //     swap(lhs.data.data, rhs.data.data);
    // }


    template <typename AnyNode>
    class NodeIterator {
       private:
        AnyNode *_ptr;

       public:
        NodeIterator(AnyNode *ptr = nullptr) :
            _ptr(ptr) {}

        void operator++() {
            this->_ptr = this->_ptr->next;
        }

        bool operator!=(const NodeIterator &it) {
            return this->_ptr != it._ptr;
        }

        // TODO: 检测是否存在嵌套的data
        AnyNode &operator*() {
            return this->_ptr->data;
        }

        AnyNode *operator->() {
            return _ptr;
        }
    };


    template <typename NodeDataType, size_t PoolSize>
    class LinkedMemoryPool {
       public:
        using NodeTypeInPool = LinkNode<NodeDataType>;

       private:
        NodeTypeInPool *_free_list = nullptr;
        NodeTypeInPool _memory_pool[PoolSize];


        void _init_free_list() {
            // 初始化后内存池中的节点按从后往前的顺序排列，free_list 指向数组中最后一个元素
            // 经过使用后，由于节点归还的顺序不固定，所以链表的顺序与数组顺序不再相关
            for (size_t i = 0; i < PoolSize; i++) {
                this->_memory_pool[i].next = this->_free_list;  // 从末端节点开始逐步初始化空闲链表
                this->_free_list = &_memory_pool[i];
            }
        }


       public:
        LinkedMemoryPool() {
            this->_init_free_list();
        }

        size_t pool_size() const {
            return PoolSize;
        }

        bool has_free_node() const {
            return _free_list != nullptr;
        }

        NodeTypeInPool *get_node_from_pool() {
            NodeTypeInPool *node = _free_list;
            if (_free_list != nullptr) {
                _free_list = _free_list->next;  // 空闲链表的节点存取都发生在头节点
            }
            return node;
        }

        void return_node_to_pool(NodeTypeInPool *node) {
            node->next = this->_free_list;
            this->_free_list = node;
        }

        // 禁止拷贝
        LinkedMemoryPool(const LinkedMemoryPool &) = delete;
        LinkedMemoryPool &operator=(const LinkedMemoryPool &) = delete;
    };


    // TODO: 再设计个全动态的伪内存池，新增节点用malloc，释放用free
    //       以及动态膨胀的内存池，新增的节点用malloc，回收节点用链表串起来备用，只获取内存，不释放，从而不会产生内存碎片
    //       动态膨胀的内存池可以打印日志，用来分析程序需要的内存池最大尺寸

    // TODO: DynamicMemoryPool
    // 动态内存池，有一个“不收缩”的选项，即内存池容量只增不减。内存池内只存储一种数据类型。
    //


    template <typename LinkedPool>
    class SimpleForwardList {
       public:
        using NodeType = typename LinkedPool::NodeTypeInPool;
        using DataType = decltype(NodeType::data);


       private:
        LinkedPool &_pool;
        NodeType *_list_head = nullptr;


       public:
        explicit SimpleForwardList(LinkedPool &memory_pool) :
            _pool(memory_pool) {}

        // explicit SimpleForwardList() : _pool(LinkedPool{}){}

        size_t max_size() const { return this->_pool.pool_size(); }

        size_t not_full() const { return this->_pool.has_free_node(); }

        size_t size() const {
            if (this->_list_head == nullptr)
                return 0;

            NodeType *temp_ptr = this->_list_head;
            size_t count = 1;
            while (temp_ptr->next != nullptr) {
                ++count;
                temp_ptr = temp_ptr->next;
            }
            return count;
        }

        bool empty() const { return this->_list_head == nullptr; }

        NodeType &front() { return *_list_head; }

        const NodeType &front() const { return *_list_head; }

        void pop_front() { this->remove(this->_list_head); }

        NodeType *find_prev_by_ptr(NodeType *target) {
            NodeType *temp_ptr = this->_list_head;

            while (temp_ptr != nullptr) {
                if (temp_ptr->next == target) {
                    return temp_ptr;
                }
                temp_ptr = temp_ptr->next;
            }

            return nullptr;
        }

        NodeType *find_prev_by_value(DataType &target_value) {
            NodeType *temp_ptr = this->_list_head;

            while (temp_ptr != nullptr) {
                if (temp_ptr->next->data == *target_value) {
                    return temp_ptr;
                }
                temp_ptr = temp_ptr->next;
            }

            return nullptr;
        }

        /**
         * @brief 删除指针指向的节点，需要遍历链表查找该节点的前驱节点
         *
         * @param that
         */
        void remove(NodeType *that) {
            NodeType *prev = find_prev_by_ptr(that);
            remove(that, prev);
        }


        void remove(const DataType &that_value) {
            NodeType *prev = find_prev_by_value(that_value);
            remove(prev->next, prev);
        }


        /**
         * @brief 用交换数据的方法快速删除节点，但只能用遍历的方式删除最后一个节点。
         *
         * 先把后一节点的数据复制到要删除的目标节点，然后删除后一节点。
         * 注意：如果外部持有列表中节点的引用或指针，这种删除方式可能会把外部持有的节点删除掉，产生野指针。
         *
         * @param that
         */
        // void remove_fast_except_end(NodeType *that) {
        //     if (that->next == nullptr) {
        //         remove(that);
        //     }
        //     that->data = that->next->data;
        //     remove(that->next, that);
        // }


        /**
         * @brief 效率较高的删除 target 指针指向的节点，回收内存
         *
         * @param target 指针指向要删除的节点，可以是第一个节点
         * @param prev   指向目标节点的前一个节点，若要删除第一个节点，则 prev 必须为 head_ptr() 的返回值
         */
        void remove(NodeType *target, NodeType *prev) {
            prev->next = target->next;
            this->_pool.return_node_to_pool(target);
        }


        /**
         * @brief 效率较高的删除 target 指针指向的节点，但不回收内存，用于将一个节点转移到其他共用内存池的表中
         *
         * @param target 指针指向要删除的节点，可以是第一个节点
         * @param prev   指向目标节点的前一个节点，若要删除第一个节点，则 prev 必须为 head_ptr() 的返回值
         */
        void remove_no_recycle(NodeType *target, NodeType *prev) {
            prev->next = target->next;
        }


        /**
         * @brief 清空链表，将所有节点逐个归还到内存池
         *
         */
        void clear() {
            while (!this->empty()) {
                this->remove(this->_list_head, this->head_ptr);
            }
        }


        // 在链表头部插入一个新节点，若剩余空闲空间不足，则函数不做任何操作，可用 has_free_space 函数在插入元素前检查
        NodeType *push_front(const DataType &data) {
            NodeType *new_node = this->_pool.get_node_from_pool();
            if (new_node == NULL)
                return nullptr;
            new_node->data = data;
            new_node->next = this->_list_head;
            this->_list_head = new_node;
            return new_node;
        }


        // 这个插入不会新创建节点，而是直接复用输入的节点，所以要保证输入的节点来自目标链表，或来自与目标链表关联的内存池，否则内存池的管理将发生混乱。
        // 这个函数可用于手动回收、移动链表内节点，或在修改节点数据后重新插入链表，还可以在多个共用内存池的链表间移动节点
        NodeType *push_front(NodeType *new_node) {
            new_node->next = this->_list_head;
            this->_list_head = new_node;
        }


        // 将节点插入到大于等于该元素的元素之前, 使链表保持从小到大的顺序, 内部数据类型要支持小于号 < 运算
        // 自始至终只使用 insert_sorted 插入元素，可保证链表从小到大顺序，否则结果随机
        // 这个插入不会新创建节点，而是直接复用输入的节点，所以要保证输入的节点来自目标链表，或来自与目标链表关联的内存池，否则内存池的管理将发生混乱。
        // 这个函数可用于手动回收、移动链表内节点，或在修改节点数据后重新插入链表，还可以在多个共用内存池的链表间移动节点
        NodeType *insert_sorted(NodeType *new_node) {
            // 查找插入位置
            NodeType *current = this->_list_head, *prev = head_ptr();
            while (current != nullptr && current->data < new_node->data) {  // 找到一个比新节点大的节点，把新节点插在前面，实现从小到大排序
                prev = current;
                current = current->next;
            }
            // 插入新节点
            // if (prev == nullptr) {  // 表示 head == NULL 或头部第一个节点就比新节点大，所以让 head 指向新节点，新节点的 next 是原来的head
            //     new_node->next = this->_list_head;
            //     this->_list_head = new_node;
            // }
            // else {                            // prev 指向比新节点大的节点的前一个节点，所以就是要把新节点插进 prev 和 current 中间
            //     new_node->next = prev->next;  // 也可以写成 new_node->next = current;
            //     prev->next = new_node;
            // }
            new_node->next = prev->next;
            prev->next = new_node;
            return new_node;
        }


        // 用输入的 data 创建新节点，将其插入到大于等于该元素的元素之前, 使链表保持从小到大的顺序, 内部数据类型要支持小于号 < 运算
        // 若剩余空闲空间不足，则函数不做任何操作，可用 has_free_space 函数在插入元素前检查
        NodeType *insert_sorted(const DataType &data) {
            NodeType *new_node = this->_pool.get_node_from_pool();
            if (new_node == nullptr)
                return nullptr;
            new_node->data = data;
            return insert_sorted(new_node);
        }


        /**
         * @brief 返回指向第一个节点前的虚拟头节点的指针，只能对其使用->next 操作，无 data 成员
         *
         * @return NodeType* 实际上是指向指向第一节点的指针的指针，即指向成员变量 list_head 的指针，
         *         可以对返回值使用 ptr->next = node_ptr 赋值语句修改 list_head，使其指向 node_ptr。
         *         由于LinkNode 中第一个成员就是 next 指针，所以指向节点的指针也可以看作指向 next 指针的指针，即指向下一个节点的二极指针。
         *         使用这种技巧的目的是在删除节点时，不用特殊对待表中的第一个节点，可以和其他节点一样修改 prev->next。
         */
        NodeType *head_ptr() { return reinterpret_cast<NodeType *>(&_list_head); }

        const NodeType *chead_ptr() const {
            return reinterpret_cast<const NodeType *>(&_list_head);
        }

        /**
         * @brief 返回指向第一个节点的指针
         *
         * @return NodeType* 指向第一个节点的指针
         */
        NodeType *begin_ptr() { return this->_list_head; }

        const NodeType *begin_ptr() const {
            return this->_list_head;
        }

        const NodeType *cbegin_ptr() const {
            return this->_list_head;
        }

        NodeType *end_ptr() const {
            return nullptr;
        }

        const NodeType *cend_ptr() const {
            return nullptr;
        }
    };


    template <typename T>
    class PtrToObject {
       private:
        T *_ptr;

       public:
        PtrToObject(T *ptr = nullptr) :
            _ptr(ptr) {}

        bool operator!=(const PtrToObject<T> &it) { return this->_ptr != it._ptr; }

        T &operator*() { return *_ptr; }

        const T &operator*() const { return *_ptr; }

        T *operator->() { return _ptr; }

        const T *operator->() const { return _ptr; }

        void swap(PtrToObject<T> &another) {
            swap(this->_ptr, another.ptr);
        }

        bool is_nullptr() const {
            return _ptr == nullptr;
        }

        const T &to_object() const {
            return *_ptr;
        }

        T &to_object() {
            return *_ptr;
        }
    };


    template <typename T>
    bool operator<(const PtrToObject<T> &left, const PtrToObject<T> &right) {
        return *left < *right;
    }


    /**
     * @brief 用来存储指向较大结构体或对象的指针，然后可以对指针排序
     *
     * 主要适用于只增不减的场合, 或一次性全部清除然后重新从头加入数据
     *
     * @tparam T
     * @tparam N
     */
    template <typename T, size_t N>
    class PointerList {
       public:
        using SizeType = enough_index_type_t<N>;

       private:
        PtrToObject<T> _ptr_list[N];

        SizeType _size = 0;

       public:
        bool empty() const {
            return _size == 0;
        }

        bool not_full() const {
            return _size != N;
        }

        SizeType size() const {
            return _size;
        }

        bool max_size() const {
            return N;
        }

        void clear() {
            _size = 0;
        }

        bool push_back(T *obj) {
            if (_size < N) {
                _ptr_list[_size] = obj;
                ++_size;
                return true;
            }
            else {
                return false;
            }
        }

        void sort() {
            auto start_it = &_ptr_list[0];
            auto end_it = &_ptr_list[_size];

            std::sort(start_it, end_it);
        }

        PtrToObject<T> &back() {
            return _ptr_list[_size - 1];
        }

        const PtrToObject<T> &back() const {
            return _ptr_list[_size - 1];
        }

        PtrToObject<T> *begin() {
            return &_ptr_list[0];
        }

        PtrToObject<T> *end() {
            return &_ptr_list[_size];
        }

        const PtrToObject<T> *begin() const {
            return &_ptr_list[0];
        }

        const PtrToObject<T> *end() const {
            return &_ptr_list[_size];
        }

        auto &get_ptr_list() {
            return _ptr_list;
        }

        const auto &get_ptr_list() const {
            return _ptr_list;
        }
    };


    template <typename T>
    struct to_signed {
    };


    template <>
    struct to_signed<uint8_t> {
        using type = int8_t;
    };


    template <>
    struct to_signed<uint16_t> {
        using type = int16_t;
    };


    template <>
    struct to_signed<uint32_t> {
        using type = int32_t;
    };


    template <>
    struct to_signed<uint64_t> {
        using type = int64_t;
    };


    template <typename T>
    using to_signed_t = typename to_signed<T>::type;


    /**
     * @brief 精简的环形队列实现
     *
     * @tparam T 数据类型
     * @tparam N 数组长度
     */
    template <typename T, size_t N, typename _IndexType = enough_index_type_t<N>>
    class RingBuffer {
       public:
        using IndexType = _IndexType;

       private:
        T _buf[N];
        IndexType _index_back = 0;
        IndexType _index_front = _dec_index(0);
        IndexType _size = 0;

        constexpr IndexType _inc_index(IndexType i) {
            if (i == N - 1)
                return 0;

            return i + 1;
        }

        constexpr IndexType _dec_index(IndexType i) {
            if (i == 0)
                return N - 1;

            return i - 1;
        }

       public:
        bool empty() const {
            return _size == 0;
        }

        /**
         * @brief 填入缓冲区的数据个数
         *
         * 返回值有可能大于N，表示有旧数据被覆盖。
         *
         * @return IndexType
         */
        IndexType size() const {
            // 由于允许头尾指针各自独立生长或收缩，只靠两个指针的相对位置不可能绝对计算出准确的缓冲区尺寸
            return _size;
        }

        size_t max_size() const {
            return N;
        }

        /**
         * @brief 缓冲区是否已满
         *
         * @return false   填入的数据个数大于或等于缓冲区尺寸
         * @return true  可以继续安全的填入数据
         */
        bool not_full() const {
            return size() < N;
        }

        void clear() {
            _index_front = _dec_index(_index_back);
            _size = 0;
        }

        /**
         * @brief 尾部追加一个元素
         *
         * 不检查剩余可用空间，当空间不足时将发生数据覆盖，此时 size() 的返回值可能大于N。
         *
         * @param val
         */
        void push_back(T val) {
            _buf[_index_back] = val;
            _index_back = _inc_index(_index_back);
            ++_size;
        }

        T pop_back() {
            _index_back = _dec_index(_index_back);
            --_size;
            return _buf[_index_back];
        }

        void push_front(T val) {
            _buf[_index_front] = val;
            _index_front = _dec_index(_index_front);
            ++_size;
        }

        T pop_front() {
            _index_front = _inc_index(_index_front);
            --_size;
            return _buf[_index_front];
        }

        /**
         * @brief 将一个数据重复填入缓冲区指定的次数
         *
         * @param val
         * @param count
         */
        void init(T val, size_t count) {
            // assert(count <= N, 'Max Size N Can Not Be Exceeded');
            while (count--) {
                push_back(val);
            }
        }

        T &back() {
            return _buf[_dec_index(_index_back)];
        }

        T &front() {
            return _buf[_inc_index(_index_front)];
        }


        const T &back() const {
            return _buf[_dec_index(_index_back)];
        }

        const T &front() const {
            return _buf[_inc_index(_index_front)];
        }
    };


    template <typename V,
              typename IndexType,
              size_t SegmentSize,
              size_t SegmentCount,
              typename InSegmentIndexType = IndexType,
              typename SegmentIndexType = enough_index_type_t<SegmentCount>>
    class StaticSegmentMappingList {
       private:
        IndexType _segment_start_index_list[SegmentCount] = {0};  // 各个分段的起始索引，必须按从小到大排列
        V _segment_list[SegmentCount][SegmentSize] = {0};

        StaticSegmentMappingList(std::initializer_list<IndexType> segment_start_index_list) :
            _segment_start_index_list(segment_start_index_list) {}
    };


}  // namespace data_basic
